/******************************************************************************

Welcome to GDB Online.
GDB online is an online compiler and debugger tool for C, C++, Python, Java, PHP, Ruby, Perl,
C#, OCaml, VB, Swift, Pascal, Fortran, Haskell, Objective-C, Assembly, HTML, CSS, JS, SQLite, Prolog.
Code, Compile, Run and Debug online from anywhere in world.

*******************************************************************************/
#include <stdio.h>
#include <stdlib.h>

typedef struct node{
    int value;
    struct node *left;
    struct node * right;
} node_t;

node_t* creatNode(int value) {
    node_t* pNode = malloc(sizeof(node_t));
    pNode->value = value;
    pNode->left = NULL;
    pNode->right = NULL;
    
    return pNode;
}

void dfs(node_t* root)
{
    if (root == NULL) {
        return;
    }   
    
    printf("%d\n", root->value);
    
    dfs(root->left);
    dfs(root->right);
}

void bfs(node_t* root)
{
    if (root == NULL) {
        return;
    }   
    
    int rear = -1;
    int front = -1;
    node_t* array[100] = {0}; //假设有100个节点

    rear = (rear + 1) % 100;
    
    array[rear] = root;
    
    while(rear != front) {
        front = (front + 1) % 100;
        node_t* current = array[front];
        printf("%d\n", current->value);
        
        if (current->left != NULL) {
            rear = (rear + 1) % 100;
            array[rear] = current->left;
        }
        
        if (current->right != NULL) {
            rear = (rear + 1) % 100;
            array[rear] = current->right;
        }
    }
}

int main()
{

    node_t* root = creatNode(1);
    root->left = creatNode(2);
    root->right = creatNode(3);
    
    root->left->left = creatNode(4);
    root->left->right = creatNode(5);
    
    printf("DFS start\n");
    dfs(root);
    
    printf("BFS start\n");
    bfs(root);

    return 0;
}
